package com.leetcode.binarytree;

import java.util.*;
import java.util.stream.Collectors;

public class BalancedTree {
    int index;

    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return height(root) != -1;
    }

    public int height(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = height(root.left);
        if(left == -1){
            return -1;
        }
        int right = height(root.right);
        if(right == -1){
            return -1;
        }
        if(Math.abs(right - left) >= 2){
            return -1;
        }
        return Math.max(left, right) + 1;
    }

    public TreeNode deserialize(String example){
        String[] strs = example.substring(1, example.length() - 1).split(",");
        List<String> treeList = Arrays.asList(strs);
//        treeList.forEach(System.out::println);
//        List<Integer> intNodes = new ArrayList<>();
//        for(String s : treeList){
//            if("null".equals(s)){
//                intNodes.add(null);
//                continue;
//            }
//            int i = Integer.parseInt(s);
//            intNodes.add(i);
//        }
//        intNodes.forEach(System.out::println);
        List<Integer> nodes = treeList.stream()
                .map(s -> "null".equals(s) ? null : Integer.parseInt(s))
                .collect(Collectors.toList());
        nodes.forEach(System.out::println);
        index = 0;
        return rdeserialize(nodes);
    }

    private TreeNode rdeserialize(List<Integer> nodes) {
        if(index >= nodes.size() || nodes.get(index) == null){
            index++;
            return null;
        }
        TreeNode node = new TreeNode(nodes.get(index++));
        node.left = rdeserialize(nodes);
        node.right = rdeserialize(nodes);
        return node;
    }

    public static void main(String[] args) {
//        由于反序列化代码为先序遍历，这里的测试案例书写方式有问题
        String example = "[1,2,2,3,3,null,null,4,4]";
        BalancedTree instance = new BalancedTree();
        TreeNode root = instance.deserialize(example);
        boolean balanced = instance.isBalanced(root);
        System.out.println(balanced);
    }
}
